public class Test1 {
    //leetcode 494 目标和
    public int findTargetSumWays(int[] nums, int target) {
        //将整数放在一起，负数放在一起，所有正数的和为a，负数和的绝对值为b,a-b = target,a + b = sum
        //a = (target + sum) / 2;从这个表达式可以得到正数和的准确值，这道题目也就是让我们在数组中找到
        //正数和为a的情况，数组中的元素为物品，物品具有体积nums[i]和价值nums[i]，这里体积和价值都是nums[i]
        //而我们的a则是背包容量

        //状态表示为：dp[i][j]表示从前i个物品中挑选物品，使得背包恰好装满时的挑选方式有几种
        int sum = 0;
        for (int n : nums) sum += n;
        int aim = (target + sum) / 2;
        if (aim < 0 || (target + sum) % 2 == 1) return 0;
        int n = nums.length;
        int[][] dp = new int[n + 1][aim + 1];
        //初始化:当i为0时，意思是从前0个物品中挑选物品，使得背包容量为1，2，3...时恰好装满，所以第0行初始化为0
        //第0列，就是从前1，2，3...个物品中选择物品，使得背包容量为0时恰好装满时的选物品的方式数目，也就是都不选
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) dp[i][j] += dp[i - 1][j - nums[i-1]];
            }
        }
        return dp[n][aim];
    }
    }

    /**
     * 一维数组优化
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays1(int[] nums, int target) {
        //将整数放在一起，负数放在一起，所有正数的和为a，负数和的绝对值为b,a-b = target,a + b = sum
        //a = (target + sum) / 2;从这个表达式可以得到正数和的准确值，这道题目也就是让我们在数组中找到
        //正数和为a的情况，数组中的元素为物品，物品具有体积nums[i]和价值nums[i]，这里体积和价值都是nums[i]
        //而我们的a则是背包容量

        //状态表示为：dp[i][j]表示从前i个物品中挑选物品，使得背包恰好装满时的挑选方式有几种
        int sum = 0;
        for (int n : nums) sum += n;
        int aim = (target + sum) / 2;
        if (aim < 0 || (target + sum) % 2 == 1) return 0;
        int n = nums.length;
        int[] dp = new int[aim + 1];
        //初始化:当i为0时，意思是从前0个物品中挑选物品，使得背包容量为1，2，3...时恰好装满，所以第0行初始化为0
        //第0列，就是从前1，2，3...个物品中选择物品，使得背包容量为0时恰好装满时的选物品的方式数目，也就是都不选
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= nums[i-1]; j--) {
                dp[j] += dp[j - nums[i-1]];
            }
        }
        return dp[aim];
    }
}
